﻿namespace LeetCodeProject._0001_1000._101_200._101_110._103;

public class Solution
{
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root)
    {
        if (root == null)
            return new List<IList<int>>();

        var nodes = new List<TreeNode>() { root };
        var results = new List<IList<int>>();
        var leftToRight = true;
        while (nodes.Count > 0)
        {
            var count = nodes.Count;
            var result = new int[count];
            if (leftToRight)
            {
                for (int i = 0; i < count; i++)
                    result[i] = nodes[i].val;
            }
            else
            {
                for (int i = 0, j = count - 1; i < count; i++, j--)
                {
                    result[j] = nodes[i].val;
                }
            }

            results.Add(result);
            for (int i = 0; i < count; i++)
            {
                var node = nodes[i];
                if (node.left != null)
                    nodes.Add(node.left);
                if (node.right != null)
                    nodes.Add(node.right);
            }

            nodes.RemoveRange(0, count);
            leftToRight = !leftToRight;
        }

        return results;
    }
}